package org.example.myleet.p798;

public class Solution {
    /**
     * 差分。关于差分参考，https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247490329&idx=1&sn=6d448a53cd722bbd990fda82bd262857&chksm=fd9cb006caeb3910758522054564348b7eb4bde333889300bd5d249950be12a5b990b5d2c059&token=168273153&lang=zh_CN#rd
     * 本题思路，观察数组的变化，按 k (0 <= k < n) 进行论调相当于整个数组所有元素向左移动k步，数组最左边的元素移动一步时将到达数组尾部（右侧），对于数组中的任意一个数字nums[i]，其能够得分有两种可能：
     * 一是当 nums[i] <= i，nums[i] 向左移动 i - nums[i] 步时，都可以得分；此外，从 i + 1 步到 i + (n - nums[i]) 步都可以得分
     * 二时当 nums[i] > i，从 i + 1 步到 i + (n - nums[i]) 步都可以得分
     * 也就是说，对于nums[i]来说，其在 k 步移动中，视其值和位置不同分类讨论，有不同的区间是可以得分的，而且区间范围的计算是O(1)复杂度的
     * 那么问题就可以转化为对多个区间进行统一+1操作，最后单点查询的问题
     * 具体操作是遍历每一个数 nums[i]，找到其得分的区间，然后+1分，最后考察每一种步数移动所得score，复杂度O(n)
     * 理解图片：
     * 差分的做法：
     * 「差分」可以看做是求「前缀和」的逆向过程。
     * 对于一个「将区间 [l, r] 整体增加一个值 」操作，我们可以对差分数组 diff 的影响看成两部分：
     * 对 diff[l] += v：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等于 l 的位置都增加了值 v；
     * 对 diff[r + 1] += v：由于我们期望只对 [l, r] 产生影响，因此需要对下标大于 r 的位置进行减值操作，从而抵消“影响”。
     * 对于最后的构造答案，可看做是对每个下标做“单点查询”操作，只需要对差分数组求前缀和即可。
     */
    public int bestRotation(int[] nums) {
        int n = nums.length, l, r;
        int[] diff = new int[n];
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= i) {
                l = 0;
                diff[l] += 1;
                r = i - nums[i];
                if (r + 1 < n) {
                    diff[r + 1] -= 1;
                }
            }
            l = i + 1;
            if (l < n) {
                diff[l] += 1;
            }
            r = i + (n - nums[i]);
            if (r + 1 < n) {
                diff[r + 1] -= 1;
            }
        }
        int[] answer = new int[n];
        answer[0] = diff[0];
        int maxScore = answer[0];
        int candidate = 0;
        for (int i = 1; i < n; ++i) {
            answer[i] = answer[i - 1] + diff[i];
            if (answer[i] > maxScore) {
                maxScore = answer[i];
                candidate = i;
            }
        }
        return candidate;
    }
}
